# 栈stack 栈顶 栈底
# 栈 后进先出 last in first out
# 进栈和出栈的次序正好相反
# 栈的特性 反转次序
# 栈 就是一个有次序的数据集， 

from pythonds.basic.stack import Stack

def baseConverter(decNumber, base):
    digits = '0123456789ABCDEF'

    remstack = Stack()

    while decNumber > 0:
        rem = decNumber % base
        remstack.push(rem)
        decNumber = decNumber // base
    
    newsting = ""
    while not remstack.isEmpty():
        newsting = newsting + digits[remstack.pop()]
    
    return newsting

print(baseConverter(25, 2))
print(baseConverter(25, 16))

# 后缀表达式求值：流程
# - 创建空栈用于暂存操作数
# - 将后缀表达式用split方法解析为单次的列表
# - 从左到右扫描单次列表
#     如果单次是操作数，则将单次转换为整数int，压入栈顶
#     如果单次是一个操作符（*/+-），则开始求值，从栈顶依次弹出两个操作数，先弹出的是右操作数，后弹出的是左操作数，计算完成后重新压入栈顶
# - 单次列表扫描结束后，表达式的值就在栈顶
# - 弹出栈顶的值，返回

def doMath(op, op1, op2):
    if op == '*':
        return op1 * op2
    elif op == '/':
        return op1 / op2
    elif op == '+':
        return op1 + op2
    elif op == '-':
        return op1 - op2

def postfixEval(postfixexpr):
    operandStack = Stack()    #创建空栈
    tokenlist = list(postfixexpr)

    for token in tokenlist:
        if token in '0123456789':
            operandStack.push(int(token))
        else:
            oper_right = operandStack.pop() # 右操作数
            oper_left = operandStack.pop()  # 左操作数
            result = doMath(token, oper_left, oper_right)
            operandStack.push(result)
    return operandStack.pop()

if __name__ == '__main__':
    print(postfixEval('233*4-42+*+'))  # 后缀表达式
                             